﻿using System.Text;

namespace Assets.Scripts.Tool
{
    public class Expression
    {
        private StackSimple<int> theStack;
        public StringBuilder suffix = new StringBuilder();

        /**
         * 检查该字符是否为括号
         */

        private bool isParen(char c)
        {
            if (c == '{' || c == '[' || c == '(' || c == ')' || c == ']' || c == '}')
                return true;
            return false;
        }

        /**
         * 检查是否为左括号
         */

        private bool isLeftParen(char c)
        {
            if (c == '{' || c == '[' || c == '(')
                return true;
            return false;
        }

        /**
         * 判断指定的操作符是否为 '+' 或者 '-'
         */

        private bool isAddOrSub(int oper)
        {
            return oper == '+' || oper == '-';
        }

        /**
         * 检查是否为数字
         */

        private bool isNumber(int ch)
        {
            return ch >= 48 && ch <= 57;
        }

        /**
         * 检查表达式是否合法
         */

        private bool CheckExp(string exp)
        {
            var ch = exp.ToCharArray();
            var theStackXInt = new StackSimple<int>(exp.Length/2);

            /**
             * 遍历表达式,只处理括号部分
             */
            for (var i = 0; i < ch.Length; i++)
            {
                var c = ch[i];
                if (isParen(c))
                {
                    /**
                     * 左括号进栈
                     */
                    if (isLeftParen(c))
                    {
                        theStackXInt.Push(c);
                    }
                    else
                    {
                        if (theStackXInt.IsEmpty())
                        {
                            return false;
                        }
                        var left = theStackXInt.Pop();
                        switch (c)
                        {
                            case '}':
                                if (left != '{')
                                    return false;
                                break;
                            case ']':
                                if (left != '[')
                                    return false;
                                break;
                            case ')':
                                if (left != '(')
                                    return false;
                                break;
                        }
                    }
                }
            }
            if (theStackXInt.IsEmpty())
            {
                return true;
            }
            return false;
        }

        /**
         * 根据当前操作符处理之前在栈中的操作符,当前操作符暂不处理,放入栈中
         */

        private void ProcessOper(char oper)
        {
            while (!theStack.IsEmpty())
            {
                var currTop = theStack.Pop();
                /**
                 * 如果是左括号,则不予处理,将括号返回进栈
                 * 
                 * 若得到的操作符,则进一步判断
                 */
                if (currTop == '(')
                {
                    theStack.Push(currTop);
                    break;
                }
                if (isAddOrSub(currTop))
                {
                    if (isAddOrSub(oper))
                    {
                        suffix.Append((char) currTop);
                    }
                    else
                    {
                        theStack.Push(currTop);
                        break;
                    }
                }
                else
                {
                    suffix.Append((char) currTop);
                    break;
                }
            }
            /**
             * 当前操作符进栈
             */
            theStack.Push(oper);
        }

        /**
         * 处理括弧.
         * 
         * 如果为左括弧,直接进栈;
         * 
         * 否则为右括弧,现将这一对括号中的操作符优先处理完
         */

        private void ProcessParen(char paren)
        {
            if (isLeftParen(paren))
            {
                theStack.Push(paren);
            }
            else
            {
                while (!theStack.IsEmpty())
                {
                    var chx = theStack.Pop();
                    if (chx == '(')
                        break;
                    suffix.Append((char) chx);
                }
            }
        }

        /**
         * 将正确的中缀表达式转为后缀表达式
         */

        private void DoTrans(string exp)
        {
            theStack = new StackSimple<int>(exp.Length);
            if (CheckExp(exp))
            {
                var ch = exp.ToCharArray();
                for (var i = 0; i < ch.Length; i++)
                {
                    var c = ch[i];
                    switch (c)
                    {
                        case '+':
                        case '-':
                        case '*':
                        case '/':
                            ProcessOper(c);
                            break;
                        case '(':
                        case ')':
                            ProcessParen(c);
                            break;

                        default:
                            suffix.Append(c);
                            break;
                    }
                }

                while (!theStack.IsEmpty())
                {
                    suffix.Append((char) theStack.Pop());
                }
            }
        }

        /**
         * 计算表达式
         */

        public int Clac(string exp)
        {
            DoTrans(exp);
            var suff = suffix.ToString();
            var stack = new StackSimple<int>(suff.Length);
            if (string.IsNullOrEmpty(suff))
            {
            }
            else
            {
                var ch = suff.ToCharArray();
                for (var i = 0; i < ch.Length; i++)
                {
                    var c = ch[i];
                    if (isNumber(c))
                    {
                        stack.Push(c - 48);
                    }
                    else
                    {
                        var operand2 = stack.Pop();
                        var operand1 = stack.Pop();
                        switch (c)
                        {
                            case '+':
                                stack.Push(operand1 + operand2);
                                break;
                            case '-':
                                stack.Push(operand1 - operand2);
                                break;
                            case '*':
                                stack.Push(operand1*operand2);
                                break;
                            case '/':
                                stack.Push(operand1/operand2);
                                break;
                        }
                    }
                }
            }
            return stack.Peep();
        }
    }
}

/// <summary>
///     用于演示栈（LIFO）的内部实现机制
///     xfeng/2010-05-07
/// </summary>
public class StackSimple<T>
{
    //栈默认的初始容量大小
    private const int DEFAULT_SIZE = 10;

    private T[] array;

    private int index;

    /// <summary>
    ///     初始化 Stack 类的新实例，该实例为空并且具有默认初始容量。
    /// </summary>
    public StackSimple()
        : this(DEFAULT_SIZE)
    {
    }

    /// <summary>
    ///     初始化 Stack 类的新实例，该实例为空并且具有指定的初始容量。
    /// </summary>
    /// <param name="size"></param>
    public StackSimple(int size)
    {
        index = -1;
        array = new T[size];
    }

    /// <summary>
    ///     获取 Stack 中包含的元素数。
    /// </summary>
    public int Count { get; private set; }

    /// <summary>
    ///     清空栈
    /// </summary>
    public void Clear()
    {
        for (var i = 0; i < array.Length; i++)
        {
            array[i] = default(T);
            index = -1;
            Count = 0;
        }
    }

    public bool IsEmpty()
    {
        return Count == 0;
    }

    /// <summary>
    ///     返回位于 Stack 顶部的对象但不将其移除。
    /// </summary>
    /// <returns>位于 Stack 顶部的 Object。</returns>
    public T Peep()
    {
        return index < 0 ? default(T) : array[index];
    }

    /// <summary>
    ///     移除并返回位于 Stack 顶部的对象。
    /// </summary>
    /// <returns>从 Stack 的顶部移除的 Object。 </returns>
    public T Pop()
    {
        var obj = index < 0 ? default(T) : array[index];
        if (null != obj)
        {
            index--;
            Count--;
            //this.array[this.index] = default(T);
        }
        return obj;
    }

    /// <summary>
    ///     将对象插入 Stack 的顶部。
    /// </summary>
    public void Push(T obj)
    {
        if (null != obj)
        {
            if (index >= array.Length - 1)
            {
                var temp = new T[array.Length*2];
                var count = 0;
                foreach (var item in array)
                {
                    temp[count++] = item;
                }
                array = temp;
            }
            array[++index] = obj;
            Count++;
        }
    }
}